#include "stdio.h"

#define MAXVEX 20
#define MAXEDGE 20
#define INFINITY 65535

typedef struct {
    int vexs[MAXVEX];
    int arc[MAXVEX][MAXVEX];
    int numNodes, numEdges;
}MGraph;

// 用于存储最短路径下标的数组
typedef int Patharc[MAXVEX][MAXVEX];
// 用于存储到各点最短路径的权值和
typedef int ShortPathTable[MAXVEX][MAXVEX];

// Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D) {
    int v, w, k;
    // 初始化
    for(v = 0; v < G.numNodes; v++) {
        // 将邻接矩阵中的权值赋给D数组，初始化P数组
        for (w = 0; w < G.numNodes; w++) {
            (*D)[v][w] = G.arc[v][w];
            (*P)[v][w] = w;
        }
    }
    // 核心算法，k代表的是中转顶点的下标, v为起始顶点, w为终止顶点
    for (k = 0; k < G.numNodes; k++) {
        for (v = 0; v < G.numNodes; v++) {
            for(w = 0; w < G.numNodes; w++) {
                // 若通过中转顶点k到达的路径长度要比直接到达的要小，则将当前的权值设置为更小的一个
                if((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    // 路径设置为经过下标为k的顶点
                    (*P)[v][w] = (*P)[v][k];
                }
            }
        }
    }

    printf("各顶点间最短路径如下：\n");
    for (v = 0; v < G.numNodes; v++) {
        for(w = v+1; w < G.numNodes; w++) {
            printf("v%d-v%d  weight:%d", v, w, (*D)[v][w]);
            // 获得第一个路径顶点下标
            k = (*P)[v][w];
            // 打印源点
            printf("path:%d", v);
            // 若路径顶点下标不是终点
            while (k!=w) {
                // 打印路径顶点
                printf("-> %d", k);
                // 获得下一个路径顶点下标
                k = (*P)[k][w];
            }
            // 打印终点
            printf("%d\n", w);
        }
        printf("\n");
    }
}
